This application is related to multicasting in communications networks and more particularly to an improved method for providing multipoint-to-multipoint multicasting in sub-packet switched communications networks.
Point-to-point communication across a communications network among a single sender and a single receiver is well known and networking protocols for point-to-point communications services are well established. Increasingly, however, a communications arrangement needs to be established among multiple senders and/or multiple receivers constituting a group having some community of interest. Accordingly, the concept of a group multicast service has evolved for enabling multiple senders to communicate to multiple receivers. It is known in the art to provide a point to multipoint connection. However, there is no present methodology for efficiently providing a multicast service between multiple senders and multiple receivers.
Networking applications can benefit in terms of scalability, performance and design simplicity from a group multicast service, i.e., a service enabling multiple senders to communicate to multiple receivers. Examples of multicasting on a broad scale include human collaboration such as video-conferencing and shared workspaces. Additionally, many applications in Local Area Networks (LANs) have often taken multicasting for granted (e.g., for address resolution, resource discovery, etc.). Moreover, it is believed that the need for multicasting will become even more pressing with the wide-scale deployment of distributed systems (e.g., maintaining replicated databases).
A number of approaches have been suggested for implementation of a multipointto-multipoint multicasting service in a communications network. In the Internet Protocol (IP) environment, two noteworthy approaches are the Core Based Tree (xe2x80x9cCBTxe2x80x9d) approach and the Protocol Independent Multicast (xe2x80x9cPIMxe2x80x9d) approach. The basic idea of CBT [see, T. Ballardie, P. Francis, and J. Crowcroft, xe2x80x9cCore Based Trees (CBT)xe2x80x9d in Proc. ACM SIGCOMM 93, (San Francisco, Calif.), September 1993] is to have a single tree per group, rooted at a core router. This tree is shared between all the senders to the group. A multicast group is set up by first choosing one (or several) core routers, and making them known to potential receivers. Receivers can then join the multicast group by sending join messages towards the core. As soon as the join message either reaches the core or a router that is part of the requested group""s tree, the new receiver is attached to the tree. Senders simply unicast packets to the core. The core then forwards packets to the receivers in the group by xe2x80x9cmulticastingxe2x80x9d the packet on the tree.
Two problems are associated with CBT. First, the reliability of the entire group is tied to the reliability of the core. If the core fails, the entire group fails. Second, the price paid by having a single tree shared by all senders sending to this group are traffic concentration and possibly increased delays as compared to having multiple sender-based shortest path trees. Moreover, the core may be a bottleneck, which contributes to the delays as a result of queuing.
PIM [see, S. Deering, et al., xe2x80x9cAn Architecture for Wide-Area Multicast Routingxe2x80x9d, in Proc. ACM SIGCOMM ""94, (London), August 1994] attempts to combine the advantages of CBT with those of sender-based shortest path trees. By default, a multicast group gets set up as a core-based tree. However, a receiver has the option to request getting packets from a given sender on the shortest path, rather than through the core-based tree. The receiver chooses the option so as to minimize the delay, which may be useful in real-time communication. Both CBT and PIM exploit point-to-multipoint capability already present in IP-based packet networks.
As sender-based trees require per-sender state both in the sender-based tree itself and the shared tree (negative-cache entries saying xe2x80x9cdo not forward packets from sender S out this interfacexe2x80x9d), a large number of senders can only be supported on the shared tree. Furthermore, the soft-state approach in PIM requires refreshing this state on a regular basis. This traffic also grows with the number of senders that are supported by sender-based trees. The operation of switching a sender from a shared to a sender-based tree is relatively costly and results in a transition period where loss can occur. Finally, joins of new receivers get more costly as the number of senders supported by sender-based trees increases (in the straightforward one-tree-per-sender case, a receiver has to join all of the trees of all of the interesting senders) because the new receiver has to learn of the existence of these senders, which happens by temporarily grafting them back onto the shared tree.
For networks based on the Asynchronous Transfer Mode (ATM) networking protocol, other multicasting approaches have been considered. At a base level, ATM multicasting may be implemented as a mesh of point-to-point virtual circuitsxe2x80x94i.e., by establishing individual point-to-point communications paths among all combinations of senders and receivers in such a multicast group. It will be apparent that such an embodiment would be highly resource intensive because each sender/receiver communications path would have to be configured using a separate virtual circuit, likely resulting in performance degradation (including duplicate transmission over the network links) as well as cost penalties. Moreover, it is often the case that virtual circuits are a scarce commodity.
It is also known in the art to implement an ATM point-to-multipoint service, wherein a xe2x80x9ctreexe2x80x9d is established representing a communications path from a single sender to multiple receivers. In such a tree, the sender can be seen as the root of the tree and each receiver as a branch of the tree. In such a point-to-multipoint service, common communications packets intended for multiple receivers are replicated at the branching point(s), rather than at the root, thus avoiding the need for redundant transmissions to those branching points. However, in order for multiple senders to multicast to a set of receivers, the use of such a point-to-multipoint approach results in multiple trees, all trying to talk to the same set of receivers.
The above limitation on multiple senders multicasting to multiple receivers has been addressed by the use of multicast serversxe2x80x94i.e., the establishment of an infrastructure of point-to-multipoint connections along with a server to achieve multipoint-to-multipoint communication. Specifically a multicast server is established to which all the senders send on distinct point-to-point circuits. The server sequences the information and sends it out on a point-to-multipoint connection to the ultimate receivers. The members of the multicast group form a multicast xe2x80x9cclusterxe2x80x9d and establish a connection to the multicast server, which itself establishes a point-to-multipoint connection to the receivers.
This approach suffers from the parallel deficiencies of requiring the dedication of a server to each multipoint-to-multipoint connection, and, where sub-packet communications networks are involved, as with ATM, also requiring reassembly of incoming sub-packets at the multicast server, before queuing them to be forwarded on the single point-to-multipoint connection to the receivers. Such a dedicated server represents not only a critical failure point that can take down the entire multicast arrangement, but also introduces significant latency as each arriving packet must be reassembled before being forwarded to the receivers. Moreover, where one or more receivers are located at a branching point between a sender and the server, it is necessary for packets to be forwarded from that sender all the way to the server and then back to the receiver, thus introducing both latency and the overhead of multiple traversal of the same path for such packets.
A system and method for implementation of multipoint-to-multipoint multicasting service in packet-based communications networks, such networks being comprised of interconnected switching nodes and transmission links defining transmission paths therein, such system and method being provided by carrying out the following steps:
specifying a unique identifier for association with each of a set of senders and receivers comprising a given multicast group;
selecting at least one switching node in such a network to act as an anchor for signalling messages sent toward that anchor from senders/receivers comprising the given multicast group;
defining a distribution tree for the given multicast group, such distribution tree including the anchor and a set of signalling paths connecting that anchor with all senders/receivers identified by that unique identifier;
causing communications paths to be established among switching nodes and transmission links included in the distribution tree, for transmission of information between senders and receivers in the given multicast group; and
where a switching node in the distribution tree includes parallel input paths, from multiple senders in the given multicast group, causing each such switching node to completely process an information segment of predefined size received from a first such input path prior to processing any portion of another information segment received from another such input path.
In a further embodiment of the invention, the system and method for implementation of multipoint-to-multipoint multicasting service carries out the further step of:
causing each switching node in a communications path in the tree to operate on an information packet from a sender transmitted toward the anchor, so as to cause a copy of such information packet to be provided directly to a receiver in the given multicast group served by a communications path connected in the tree hierarchy at or below the location of that switching node, whereby only information packets destined to receivers served by communications paths connected in the tree hierarchy at or beyond the anchor need be transmitted to and processed by the anchor.